package 力扣._279完全平方数;

public class Solution {
    public int numSquares(int n) {
        //物品重量：1 , 2*2, 3*3
        //背包容量 n
        //物品无限使用——》完全背包
        //dp[j]:容量为j的背包至少需要dp[i]个完全平方数才能装满
        //dp[j] = min(dp[j - i*i] +1, dp[j])
        //则要初始化为最大值 n+1
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = 99999999;
        }
        for (int i = 0; i * i <= n; i++) {  //
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}
